Kõnig's line coloring and Vizing's theorems for graphings
Endre Csóka


Abstract

The classical theorem of Vizing states that every graph of maximum degree d admits an edge-coloring with at most d+1 colors. Furthermore, as it was earlier shown by Kõnig, d colors suffice,
if the graph is bipartite.

We investigate the existence of measurable edge-colorings for graphings (or measure-preserving graphs). A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence and measurable group theory.  We show that every graphing of maximum degree d admits a measurable edge-coloring with d+O(sqrt d) colors;
furthermore,  if  the  graphing  has  no  odd  cycles,  then d+1  colors  suffice.   In  fact,  if  a  certain conjecture about finite graphs that strengthens Vizing’s theorem is true, then our method will show that d+1 colors are always enough.